﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LevenshteinDistance
{
    public static class Levenshtein
    { 
        // to calculate the similarity degree
        public static int Distance(string str1, string str2)
        {
            if (str1.Length == 0)
            {
                return str2.Length;
            }
            if (str2.Length == 0)
            {
                return str1.Length;
            }

            int n = str1.Length, m = str2.Length;
            int[][] MatD = new int[n + 1][];
            for (int i = 0; i <= n; i++)
            {
                MatD[i] = new int[m + 1];
            }

            // Init
            for (int i = 0; i <= n; i++)
            {
                MatD[i][0] = i;
            }
            for (int i = 0; i <= m; i++)
            {
                MatD[0][i] = i;
            }

            // Calc
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    int cost = ((str1[i - 1] == str2[j - 1]) ? 0 : 1);
                    MatD[i][j] = Math.Min(Math.Min(MatD[i - 1][j] + 1, MatD[i][j - 1] + 1), MatD[i - 1][j - 1] + cost);
                }
            }

            return MatD[n][m];
        }

        public static double SimilarityDegree(string s1, string s2)
        {
            StringBuilder sbdr1 = new StringBuilder();
            StringBuilder sbdr2 = new StringBuilder();

            foreach (var v in s1)
            {
                if (v != '\t' && v != '\n' && v != '\r' && v != ' ')
                {
                    sbdr1.Append(v);
                }
            }
            foreach (var v in s2)
            {
                if (v != '\t' && v != '\n' && v != '\r' && v != ' ')
                {
                    sbdr2.Append(v);
                }
            }

            string str1 = sbdr1.ToString();
            string str2 = sbdr2.ToString();

//             Console.WriteLine(str1);
//             Console.WriteLine(str2);

            double t = (double)Distance(str1, str2);
            return 1.0 - 2.0 * t / ((double)(str1.Length + str2.Length));
            // return strange value
//            return t/(t + s1.Length + s2.Length);
        }

        // strange function
        public static decimal GetSimilarityWith(string src, string str)
        {
            string s1 = "", s2 = "";
            foreach (var v in src)
            {
                if (v != '\n' && v != ' ' && v != '\t')
                {
                    s1 += v;
                }
            }
            foreach (var v in str)
            {
                if (v != '\n' && v != ' ' && v != '\t')
                {
                    s2 += v;
                }
            }
            decimal Kq = 2;
            decimal Kr = 1;
            decimal Ks = 1;
            char[] ss = s1.ToCharArray();
            char[] st = s2.ToCharArray();

            int q = ss.Intersect(st).Count();
            int s = ss.Length - q;
            int r = st.Length - q;

            return Kq*q/(Kq*q + Kr*r + Ks*s);
        }
    }
}
